{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ways to Split Array Into Three Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToSplit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组分成三个子数组的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们称一个分割整数数组的方案是 <strong>好的</strong> ，当它满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>数组被分成三个 <strong>非空</strong> 连续子数组，从左至右分别命名为 <code>left</code> ， <code>mid</code> ， <code>right</code> 。</li>\n",
    "\t<li><code>left</code> 中元素和小于等于 <code>mid</code> 中元素和，<code>mid</code> 中元素和小于等于 <code>right</code> 中元素和。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个 <strong>非负</strong> 整数数组 <code>nums</code> ，请你返回 <strong>好的</strong> 分割 <code>nums</code> 方案数目。由于答案可能会很大，请你将结果对 <code>10<sup>9 </sup>+ 7</code> 取余后返回。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,2,2,5,0]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>nums 总共有 3 种好的分割方案：\n",
    "[1] [2] [2,2,5,0]\n",
    "[1] [2,2] [2,5,0]\n",
    "[1,2] [2,2] [5,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,2,1]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有好的分割方案。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ways-to-split-array-into-three-subarrays](https://leetcode.cn/problems/ways-to-split-array-into-three-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ways-to-split-array-into-three-subarrays](https://leetcode.cn/problems/ways-to-split-array-into-three-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1]', '[1,2,2,2,5,0]', '[3,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        j = k = 0\n",
    "\n",
    "        sums = sum(nums)\n",
    "        left = 0\n",
    "        mid1 = nums[0]\n",
    "        mid2 = nums[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left += nums[i]\n",
    "            mid1 -= nums[i]\n",
    "            mid2 -= nums[i]\n",
    "            while j == i or mid1 < left:\n",
    "                j += 1\n",
    "                if j < n:\n",
    "                    mid1 += nums[j]\n",
    "                else:\n",
    "                    break    \n",
    "            \n",
    "            if j >= n - 1:\n",
    "                break\n",
    "\n",
    "            while k < n - 2 and mid2 <= sums - left - mid2:  #为了保证right不为空\n",
    "                nxt = mid2 + nums[k+1]\n",
    "                if sums - left - nxt >= nxt:\n",
    "                    k += 1\n",
    "                    mid2 += nums[k]\n",
    "                else:\n",
    "                    break\n",
    "            if k >= n - 1:\n",
    "                break\n",
    "            if i < j and k >= j and mid2 <= sums - left - mid2:\n",
    "                ans += k - j + 1\n",
    "                ans %= 10 ** 9 + 7\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        j = k = 0\n",
    "\n",
    "        sums = sum(nums)\n",
    "        left = 0\n",
    "        mid1 = nums[0]\n",
    "        mid2 = nums[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left += nums[i]\n",
    "            mid1 -= nums[i]\n",
    "            mid2 -= nums[i]\n",
    "            while j == i or mid1 < left:\n",
    "                j += 1\n",
    "                if j < n:\n",
    "                    mid1 += nums[j]\n",
    "                else:\n",
    "                    break    \n",
    "            \n",
    "            if j >= n - 1:\n",
    "                break\n",
    "\n",
    "            while k < n - 2 and mid2 <= sums - left - mid2:  #为了保证right不为空\n",
    "                nxt = mid2 + nums[k+1]\n",
    "                if sums - left - nxt >= nxt:\n",
    "                    k += 1\n",
    "                    mid2 += nums[k]\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            if k >= j and mid2 <= sums - left - mid2:\n",
    "                ans += k - j + 1\n",
    "                ans %= 10 ** 9 + 7\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        j = k = 0\n",
    "\n",
    "        sums = sum(nums)\n",
    "        left = 0\n",
    "        mid1 = nums[0]\n",
    "        mid2 = nums[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left += nums[i]\n",
    "            mid1 -= nums[i]\n",
    "            mid2 -= nums[i]\n",
    "            while j == i or mid1 < left:\n",
    "                j += 1\n",
    "                if j < n:\n",
    "                    mid1 += nums[j]\n",
    "                else:\n",
    "                    break    \n",
    "            \n",
    "            if j >= n - 1:\n",
    "                break\n",
    "\n",
    "            while k < n - 2 and mid2 <= sums - left - mid2:  #为了保证right不为空\n",
    "                nxt = mid2 + nums[k+1]\n",
    "                if sums - left - nxt >= nxt:\n",
    "                    k += 1\n",
    "                    mid2 += nums[k]\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            if i < j and k >= j and mid2 <= sums - left - mid2:\n",
    "                ans += k - j + 1\n",
    "                ans %= 10 ** 9 + 7\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        l, ans, s = len(nums), 0, sum(nums)\n",
    "        M = int(1e9 + 7)\n",
    "        # 前缀和预处理\n",
    "        for i in range(1, l):\n",
    "            nums[i] += nums[i - 1]\n",
    "        # 以i为左边界\n",
    "        for i in range(0, l):\n",
    "            # 寻找的中间节点的左边界\n",
    "            le = nums[i] << 1\n",
    "            # 中间节点右边界\n",
    "            re = (s - nums[i] >> 1) + nums[i]\n",
    "            # 左节点为 lower_bound,右节点为upper_bound, 为了特殊处理 全0 的数据\n",
    "            t1, t2 = bisect.bisect_left(nums, le), bisect.bisect_right(nums, re)\n",
    "            # 如果前面的数全为0，查找的t1 会为0，这是应该将 t1 更新为 i + 1\n",
    "            if t1 <= i: t1 = i + 1\n",
    "            # nums[t2] 为大于re的点，在边界的右边，需自减\n",
    "            t2 = t2 - 1\n",
    "            # t2 应该小于l - 1,右区间至少一个节点\n",
    "            if t2 == l - 1:t2 -= 1\n",
    "            # 如果左边界小于等于右边界，说明 以 i 为 左边界，t2 --- t1 之间为右边界的所有节点均满足要求，所以满足边界的数量为 t2 - t1 + 1\n",
    "            if t1 <= t2:\n",
    "                ans += t2 - t1 + 1\n",
    "                ans %= M\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i+1,bisect_left(pre,pre[i]+pre[i]))\n",
    "            r = min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))\n",
    "            ans = (ans + max(0,r - l)) % mod\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        j = k = 0\n",
    "\n",
    "        sums = sum(nums)\n",
    "        left = 0\n",
    "        mid1 = nums[0]\n",
    "        mid2 = nums[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left += nums[i]\n",
    "            mid1 -= nums[i]\n",
    "            mid2 -= nums[i]\n",
    "            while j == i or mid1 < left:\n",
    "                j += 1\n",
    "                if j < n:\n",
    "                    mid1 += nums[j]\n",
    "                else:\n",
    "                    break    \n",
    "            \n",
    "            if j >= n - 1:\n",
    "                break\n",
    "\n",
    "            while k < n - 2:  #为了保证right不为空\n",
    "                nxt = mid2 + nums[k+1]\n",
    "                if sums - left - nxt >= nxt:\n",
    "                    k += 1\n",
    "                    mid2 += nums[k]\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            if k >= j and mid2 <= sums - left - mid2:\n",
    "                ans += k - j + 1\n",
    "                ans %= 10 ** 9 + 7\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "        l, m, r = 0, 1, 1\n",
    "        # 第一条分界线最多到 nums[l] * 3 <= nums[n - 1]\n",
    "        while l < n - 2 and nums[l] * 3 <= nums[n - 1]:\n",
    "            m = max(m, l + 1)\n",
    "            # 第二条线最左\n",
    "            while (m < n - 1 and nums[m] < nums[l] * 2):\n",
    "                m += 1\n",
    "            # 第二条线最右边\n",
    "            while (r < n - 2 and nums[r + 1] - nums[l] <= nums[n - 1] - nums[r + 1]):\n",
    "                r += 1\n",
    "            ans = (ans + r - m + 1) % MOD\n",
    "            l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i+1,bisect_left(pre,pre[i]+pre[i]))\n",
    "            r = min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))\n",
    "            ans = (ans + max(0,r - l)) % mod\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        pre = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            pre.append(pre[-1] + nums[i])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i + 1, bisect_left(pre, pre[i] + pre[i]))\n",
    "            r = min(n - 1, bisect_right(pre, (pre[i] + pre[-1]) // 2))\n",
    "            ans = (ans + max(0, r - l)) % mod\n",
    "        return ans % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mod=10**9+7\n",
    "        for i in range(1,n):\n",
    "            nums[i]+=nums[i-1]\n",
    "        tot=nums[-1]\n",
    "        ret=0\n",
    "        for i in range(n):\n",
    "            if 3*nums[i]>tot :\n",
    "                break \n",
    "            l,r=i+1,n-1\n",
    "            # 求大于一个数的最左index,左0右1\n",
    "            while l<r:\n",
    "                m=(l+r)//2\n",
    "                if nums[m]-nums[i]>=nums[i]:\n",
    "                    r=m\n",
    "                else :\n",
    "                    l=m+1\n",
    "            j=r \n",
    "            l,r=i+1,n-1\n",
    "            # 求小于一个数的最右index，左1右0\n",
    "            while l<r:\n",
    "                m=(l+r)//2\n",
    "                if tot-nums[m]>=nums[m]-nums[i]:\n",
    "                    l=m+1\n",
    "                else:\n",
    "                    r=m\n",
    "            k=r \n",
    "            ret+=(k-j)\n",
    "        return ret%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        #j为mid的最左边位置(包括j)\n",
    "        #k为mid的最右边位置(不包括k)\n",
    "        j = 0\n",
    "        k = 0\n",
    "\n",
    "        sums = sum(nums)\n",
    "        left = 0\n",
    "        mid1 = nums[0]\n",
    "        mid2 = nums[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left += nums[i]\n",
    "            mid1 -= nums[i]\n",
    "            mid2 -= nums[i]\n",
    "            while j == i or mid1 < left:\n",
    "                j += 1\n",
    "                if j < n:\n",
    "                    mid1 += nums[j]\n",
    "                else:\n",
    "                    break    \n",
    "            \n",
    "            if j >= n - 1:\n",
    "                break\n",
    "\n",
    "            while k <= i or (k < n - 1 and mid2 <= sums - left - mid2):\n",
    "                k += 1\n",
    "                mid2 += nums[k]\n",
    "\n",
    "            if k >= j:\n",
    "                #print(i, j, k)\n",
    "                ans += k - j\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        MOD = 10**9 + 7\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "        l, m, r = 0, 1, 1\n",
    "        while l < n - 2 and nums[l] * 3 <= nums[n - 1]:\n",
    "            m = max(m, l + 1)\n",
    "            while (m < n - 1 and nums[m] < nums[l] * 2):\n",
    "                m += 1\n",
    "            while (r < n - 2 and nums[r + 1] - nums[l] <= nums[n - 1] - nums[r + 1]):\n",
    "                r += 1\n",
    "            ans = (ans + r - m + 1) % MOD\n",
    "            l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        prefix = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            prefix.append(prefix[-1]+ nums[i])\n",
    "            \n",
    "        res = 0\n",
    "        Mod = 10**9+7\n",
    "        \n",
    "        for i in range(len(prefix)):\n",
    "            firstseg = prefix[i]\n",
    "            if firstseg*3 > prefix[-1]:break\n",
    "            \n",
    "            second_first_seg = firstseg*2\n",
    "            second_first_seg_pos = bisect.bisect_left(prefix, second_first_seg, i+1)\n",
    "            \n",
    "            second_second_seg = (prefix[i] + prefix[-1])//2\n",
    "            second_second_seg_pos = bisect.bisect_right(prefix, second_second_seg, second_first_seg_pos+1)\n",
    "            \n",
    "            if second_second_seg_pos > len(nums) or prefix[second_second_seg_pos-1] > second_second_seg:continue\n",
    "            res = (res + (min(len(nums)-1, second_second_seg_pos) - second_first_seg_pos))%Mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i + 1, bisect_left(pre, 2 * pre[i]))\n",
    "            r = min(n-1, bisect_right(pre, (pre[-1] + pre[i]) //2))\n",
    "            ans += max(0, (r - l)) % MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        pre = list(accumulate(nums))\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            left = max(i+1, bisect_left(pre, pre[i] + pre[i]))\n",
    "            right = min(n-1, bisect_right(pre, (pre[i]+pre[-1])//2))\n",
    "            if left < right:\n",
    "                ret += (right-left)\n",
    "        return ret % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "        res = 0\n",
    "        i = 0\n",
    "        j = 1\n",
    "        k = 1\n",
    "        while i < n - 2 and nums[i] * 3 <= nums[n - 1]:\n",
    "            j = max(i + 1, j)\n",
    "\n",
    "            while j < n - 1 and nums[j] < 2 * nums[i]:\n",
    "                j += 1\n",
    "            while k < n -2 and nums[k + 1] <= (nums[n - 1] + nums[i]) / 2:\n",
    "                k += 1\n",
    "            res += k - j + 1\n",
    "            i += 1\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i+1,bisect_left(pre,pre[i]+pre[i]))\n",
    "            r = min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))\n",
    "            ans = (ans + max(0,r - l)) % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "        left, right1, right2 = 0, 0, 0\n",
    "        ans = 0\n",
    "        while left < n - 2:\n",
    "            sum1 = nums[left]\n",
    "            if right1 <= left:\n",
    "                right1 = left + 1\n",
    "            while right1 < n - 1 and nums[right1] < 2*sum1:\n",
    "                right1 += 1\n",
    "            if right1 > n - 2 and nums[right1] < 2*sum1:\n",
    "                break\n",
    "            while right2 < n - 1 and 2*nums[right2] <= nums[-1] + sum1:\n",
    "                right2 += 1\n",
    "            ans += max(right2 - right1, 0)\n",
    "            left += 1\n",
    "\n",
    "        return ans%(10**9+7)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i+1,bisect_left(pre,pre[i]+pre[i]))\n",
    "            r = min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))\n",
    "            ans = (ans + max(0,r - l)) % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        i = 0\n",
    "        j = 1\n",
    "        k = 1\n",
    "        while i < n - 2 and nums[i] * 3 <= nums[n - 1]:\n",
    "            j = max(i + 1, j)\n",
    "\n",
    "            while j < n - 1 and nums[j] < 2 * nums[i]:\n",
    "                j += 1\n",
    "            while k < n -2 and nums[k + 1] <= (nums[n - 1] + nums[i]) / 2:\n",
    "                k += 1\n",
    "            res += k - j + 1\n",
    "            i += 1\n",
    "        return res % MOD\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#从BF出发优化\n",
    "# 在前缀和上枚举两个指针\n",
    "# 优化：第一个指针确定后，可以根据数学关系，列出不等式，从而是用二分确定第二个指针的范围\n",
    "# 范围查找应想到二分，等值查找想到hashmap\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums:List[int]) -> int:\n",
    "        #  查找nums中>=target的第一个位置\n",
    "        n=len(nums)\n",
    "        # 计算前缀和\n",
    "        summ=[0]*n\n",
    "        summ[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            summ[i]=summ[i-1]+nums[i]\n",
    "\n",
    "        def lower_bound(start,target):\n",
    "            l,r=start,n-2\n",
    "            while l<r:\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l if l<n-1 and target<=summ[l] else -1\n",
    "\n",
    "        def upper_bound(start,target):\n",
    "            l,r=start,n-2\n",
    "            while l<r:\n",
    "                mid=((r-l)>>1)+l+1\n",
    "                if summ[mid]<=target:\n",
    "                    l=mid\n",
    "                else:\n",
    "                    r=mid-1\n",
    "            return r if r<n-1 and target>=summ[r] else -1\n",
    "        \n",
    "        \n",
    "        # 枚举第一个指针\n",
    "        ans=0\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(n):\n",
    "            if 3*summ[i]>summ[n-1]:\n",
    "                break\n",
    "            left=lower_bound(i+1,2*summ[i])\n",
    "            if left==-1:\n",
    "                continue\n",
    "\n",
    "            right=upper_bound(i+1,(summ[n-1]+summ[i])*0.5)\n",
    "            if right==-1:\n",
    "                continue\n",
    "            ans=(ans%mod+(right-left+1)%mod)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        i = 0\n",
    "        j = 1\n",
    "        k = 1\n",
    "        while i < n - 2 and nums[i] * 3 <= nums[n - 1]:\n",
    "            j = max(i + 1, j)\n",
    "\n",
    "            while j < n - 1 and nums[j] < 2 * nums[i]:\n",
    "                j += 1\n",
    "            while k < n - 2 and nums[k + 1] <= (nums[n - 1] + nums[i]) / 2:\n",
    "                k += 1\n",
    "            res += k - j + 1\n",
    "            i += 1\n",
    "        return res % MOD\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + x\n",
    "        total = prefix_sum[-1]\n",
    "        right1 = right2 = 0\n",
    "        ans = 0\n",
    "\n",
    "        for left in range(n - 1):\n",
    "            x = prefix_sum[left + 1]\n",
    "            if right1 <= left + 1:\n",
    "                right1 = left + 2\n",
    "            while right1 < n and prefix_sum[right1] < 2 * x:\n",
    "                right1 += 1\n",
    "            if right1 >= n and prefix_sum[right1] < 2 * x:\n",
    "                break\n",
    "            while right2 < n and prefix_sum[right2] <= (total + x) // 2:\n",
    "                right2 += 1\n",
    "            ans += max(right2 - right1, 0)\n",
    "        \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n, ans, mod = len(nums), 0, int(1e9+7)\n",
    "        preSum = [0 for _ in range(n+1)] #  前缀和\n",
    "        for i in range(1,n+1):\n",
    "            preSum[i] = preSum[i-1] + nums[i-1] \n",
    "        # |______|________|_______|________|\n",
    "        # 1      i        l       r        n\n",
    "        # i 表示第一刀的位置，枚举第一刀的位置，计算第二刀的可选位置数mid属于[l,r），这样三个子数组:nums[0,i][i,j][j,n]\n",
    "        l, r = 2, 2\n",
    "        for i in range(1,n):\n",
    "            l = max(l,i+1) # 子数组[i,l]不能为空\n",
    "            r = max(r,i+1) # 子数组[i,r]不能为空\n",
    "            # Sum(right) >= Sum(mid)，r最大为n-1，right保证要有一个数\n",
    "            while r <= n - 1 and preSum[n] - preSum[r] >= preSum[r] - preSum[i]: # 右边大于中间\n",
    "                r += 1 \n",
    "            # Sum(mid) >= Sum(left)\n",
    "            while l <= n - 1 and preSum[l] - preSum[i] < preSum[i]: # 中间大于左边\n",
    "                l += 1 \n",
    "            if l <= r:  # 第二刀可选区间[l,r）不为空\n",
    "                ans += r - l \n",
    "        return int(ans % int(1e9+7)) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        # step 1: 都是正数，用prefix, 现在有单调性\n",
    "        prefix = [0]\n",
    "        for num in nums:\n",
    "            prefix.append(prefix[-1] + num)\n",
    "    \n",
    "        # prefix[i] <= prefix[j]-prefix[i] <= prefix[-1]-prefix[j]\n",
    "        #part 1: => prefix[i]*2 <= prefix[j] \n",
    "        # part 2: prefix[j] <= (prefix[-1]+prefix[i])/2\n",
    "        # find the range of j: lower <= j < upper\n",
    "        # step 2: 每个i 固定后，j的可能范围（上下界）\n",
    "        ways = 0\n",
    "        for i in range(1, len(prefix)-2):\n",
    "            # lower = lower bound of j （第一个符合条件的j)\n",
    "            lower = bisect_left(prefix, prefix[i]*2) # prefix[i]*2 <= prefix[j]\n",
    "            # upper = (upper bound of j) + 1 (最后一个符合跳的j之后一个index)\n",
    "            upper = bisect_right(prefix, (prefix[-1]+prefix[i])/2) # prefix[j] <= (prefix[-1]+prefix[i])/2\n",
    "            # i+1 <= lower < upper <= len(prefix)-1\n",
    "            ways += max(0, min(upper, len(prefix)-1) - max(lower, i+1))\n",
    "        return ways % (10**9+7)\n",
    "# https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/discuss/999157/Python3-binary-search-and-2-pointer  \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ps = list(accumulate(nums))\n",
    "\n",
    "        def check(mid):\n",
    "            return ps[-1] - ps[mid] >= ps[mid] - ps[i]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n - 2):\n",
    "            l = max(i + 1, bisect_left(ps, ps[i] * 2))\n",
    "\n",
    "            r = min(n - 2, bisect_left(range(n - 1), 1, l, key=lambda t: not check(t)) - 1)\n",
    "            if r >= l:\n",
    "                ans += r - l + 1\n",
    "                ans %= kmod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#从BF出发优化\n",
    "# 在前缀和上枚举两个指针\n",
    "# 优化：第一个指针确定后，可以根据数学关系，列出不等式，从而是用二分确定第二个指针的范围\n",
    "# 范围查找应想到二分，等值查找想到hashmap\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums:List[int]) -> int:\n",
    "        #  查找nums中>=target的第一个位置\n",
    "        n=len(nums)\n",
    "        # 计算前缀和\n",
    "        summ=[0]*n\n",
    "        summ[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            summ[i]=summ[i-1]+nums[i]\n",
    "\n",
    "        def lower_bound(start,target):\n",
    "            l,r=start,n-2\n",
    "            # if l>r:\n",
    "            #     return -1\n",
    "            while l<r:\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l if l<n-1 and target<=summ[l] else -1\n",
    "\n",
    "        def upper_bound(start,target):\n",
    "            l,r=start,n-2\n",
    "            while l<r:\n",
    "                mid=((r-l)>>1)+l+1\n",
    "                if summ[mid]<=target:\n",
    "                    l=mid\n",
    "                else:\n",
    "                    r=mid-1\n",
    "            return r if r<n-1 and target>=summ[r] else -1\n",
    "        \n",
    "        \n",
    "        # 枚举第一个指针\n",
    "        ans=0\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(n):\n",
    "\n",
    "            if 3*summ[i]>summ[n-1]:\n",
    "                break\n",
    "            left=lower_bound(i+1,2*summ[i])\n",
    "            if left==-1:\n",
    "                continue\n",
    "\n",
    "            right=upper_bound(i+1,(summ[n-1]+summ[i])*0.5)\n",
    "            if right==-1:\n",
    "                continue\n",
    "            ans=(ans%mod+(right-left+1)%mod)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#从BF出发优化\n",
    "# 在前缀和上枚举两个指针\n",
    "# 优化：第一个指针确定后，可以根据数学关系，列出不等式，从而是用二分确定第二个指针的范围\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums:List[int]) -> int:\n",
    "        #  查找nums中>=target的第一个位置\n",
    "        n=len(nums)\n",
    "        # 计算前缀和\n",
    "        summ=[0]*n\n",
    "        summ[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            summ[i]=summ[i-1]+nums[i]\n",
    "\n",
    "        def lower_bound(start,target):\n",
    "            l,r=start,n-2\n",
    "            # if l>r:\n",
    "            #     return -1\n",
    "            while l<r:\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l if l<n-1 and target<=summ[l] else -1\n",
    "\n",
    "        def upper_bound(start,target):\n",
    "            l,r=start,n-2\n",
    "            # if l>r:\n",
    "            #     return -1\n",
    "            while l<r:\n",
    "                mid=((r-l)>>1)+l+1\n",
    "                if summ[mid]<=target:\n",
    "                    l=mid\n",
    "                else:\n",
    "                    r=mid-1\n",
    "            return r if r<n-1 and target>=summ[r] else -1\n",
    "        \n",
    "        \n",
    "        # 枚举第一个指针\n",
    "        ans=0\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(n):\n",
    "            # lower_bound:sum[j]-sum[i]>=sum[i]=>\n",
    "            # 2*sum[i]<=sum[j]\n",
    "            if 3*summ[i]>summ[n-1]:\n",
    "                break\n",
    "            left=lower_bound(i+1,2*summ[i])\n",
    "            if left==-1:\n",
    "                continue\n",
    "            # print(\"left:\",left,\"i:\",i)\n",
    "            # sum[n]-sum[j]>=sum[j]-sum[i]\n",
    "            # =>2*sum[j]<=sum[n]+sum[i]\n",
    "            right=upper_bound(i+1,(summ[n-1]+summ[i])*0.5)\n",
    "            if right==-1:\n",
    "                continue\n",
    "            # print(\"right:\",right)\n",
    "            ans=(ans%mod+(right-left+1)%mod)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        \n",
    "        # Calculate prefix sums\n",
    "        prefix = [0] * n\n",
    "        prefix[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + nums[i]\n",
    "\n",
    "        def canSplit(j, k):\n",
    "            return prefix[j] <= prefix[k] - prefix[j] and prefix[k] - prefix[j] <= prefix[-1] - prefix[k]\n",
    "\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(n - 2):\n",
    "            while j < i + 1 or (j < n - 1 and prefix[j] - prefix[i] < prefix[i]):\n",
    "                j += 1\n",
    "            if j == n - 1:\n",
    "                break\n",
    "            low, high = j, n - 2\n",
    "            while low < high:\n",
    "                mid = (low + high + 1) // 2\n",
    "                if canSplit(i, mid):\n",
    "                    low = mid\n",
    "                else:\n",
    "                    high = mid - 1\n",
    "            if canSplit(i, j):\n",
    "                ans += low - j + 1\n",
    "                ans %= MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * n\n",
    "        s[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            s[i] = s[i - 1] + nums[i]\n",
    "        ret = 0\n",
    "\n",
    "        M = 10 ** 9 + 7\n",
    "        ret = 0\n",
    "        mid = right = 1\n",
    "        tot = 0\n",
    "        for left in range(n - 2):\n",
    "            \n",
    "            lefts = s[left]\n",
    "            mid = max(mid, left + 1)\n",
    "            while mid <= n - 2 and lefts > s[mid] - lefts:\n",
    "                mid += 1\n",
    "            \n",
    "            if mid > n - 2:\n",
    "                break\n",
    "            if s[n - 1] - s[mid] < s[mid] - lefts:\n",
    "                continue\n",
    "            right = max(mid, right)\n",
    "            while right + 2 < n and s[n - 1] - s[right + 1] >= s[right + 1] - lefts:\n",
    "                right += 1\n",
    "            ret += right - mid + 1\n",
    "       \n",
    "        return ret % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#从BF出发优化\n",
    "# 在前缀和上枚举两个指针\n",
    "# 优化：第一个指针确定后，可以根据数学关系，列出不等式，从而是用二分确定第二个指针的范围\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums:List[int]) -> int:\n",
    "        #  查找nums中>=target的第一个位置\n",
    "        n=len(nums)\n",
    "        # 计算前缀和\n",
    "        summ=[0]*n\n",
    "        summ[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            summ[i]=summ[i-1]+nums[i]\n",
    "\n",
    "        def lower_bound(start,target):\n",
    "            l,r=start,n-1\n",
    "            if l>r:\n",
    "                return -1\n",
    "            while l<r:\n",
    "                # print(l,r)\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l\n",
    "\n",
    "        def upper_bound(start,target):\n",
    "            l,r=start,n-1\n",
    "            if l>r:\n",
    "                return -1\n",
    "            while l<r:\n",
    "                # print(l,r)\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<=target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l-1\n",
    "        \n",
    "        \n",
    "        # 枚举第一个指针\n",
    "        ans=0\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(n):\n",
    "            # lower_bound:sum[j]-sum[i]>=sum[i]=>\n",
    "            # 2*sum[i]<=sum[j]\n",
    "            if 3*summ[i]>summ[n-1]:\n",
    "                break\n",
    "            left=lower_bound(i+1,2*summ[i])\n",
    "            if left==-1:\n",
    "                continue\n",
    "            # print(\"left:\",left,\"i:\",i)\n",
    "            # sum[n]-sum[j]>=sum[j]-sum[i]\n",
    "            # =>2*sum[j]<=sum[n]+sum[i]\n",
    "            right=upper_bound(i+1,(summ[n-1]+summ[i])*0.5)\n",
    "            if right==-1:\n",
    "                continue\n",
    "            # print(\"right:\",right)\n",
    "            ans=(ans%mod+(right-left+1)%mod)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "1. 先思考一个简单的问题：分成两个子数组\n",
    "s1\n",
    "s2 = sum(nums) - s1\n",
    "s1 <= s2\n",
    "s1 <= sum(nums) - s1\n",
    "\n",
    "2*s1 <= sum(nums)\n",
    "s1 <= sum(nums)//2\n",
    "\n",
    "2. 分成三个子数组\n",
    "枚举第三个子数组\n",
    "s1 + s2 + s3 = sum(nums)\n",
    "\n",
    "s1 + s2 = sum(nums) - s3\n",
    "s1 <= s2 <= sum(nums) - s1 - s2\n",
    "\n",
    "s1 <= s2\n",
    "s1 <= sum(nums) - 2*s2\n",
    "\n",
    "s1 <= s2 <= (sum(nums) - s1)//2\n",
    "\n",
    "在固定 s3 的前提下（s2 的右端点是固定的）\n",
    "有多少个合法的 s2\n",
    "求出 s2 的最小值（s2 左端点的最大值）\n",
    "求出 s2 的最大值（s2 左端点的最小值） 最小是 1\n",
    "\n",
    "s1 + s2 = sum(nums) - s3\n",
    "s1 <= s2\n",
    "得到 s2 的最小值 = (sum(nums) - s3 + 1) // 2\n",
    "\n",
    "s2 的最大值 = s3\n",
    "\n",
    "3. 用下标分析\n",
    "s3 = sum[n] - sum[j]\n",
    "s2 = sum[j] - sum[il]\n",
    "s2 <= s3  => sum[il] >= 2*sum[j] - sum[n]\n",
    "j 越大，il 越大\n",
    "\n",
    "s2 = sum[j] - sum[ir]\n",
    "s1 = sum[ir]\n",
    "s1 <= s2  => sum[ir] <= sum[j]//2\n",
    "j 越大，ir 越大\n",
    "\n",
    "j 的下界：2\n",
    "\n",
    "j 的上界\n",
    "sum[il] >= 2*sum[j] - sum[n]\n",
    "sum[ir] <= sum[j]//2\n",
    "=> 3*sum[j] <= 2*sum[n]\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sum = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            sum[i+1] = sum[i] + x\n",
    "\n",
    "        ans = 0\n",
    "        il = 1  # 第二个子数组的左端点\n",
    "        ir = 1\n",
    "        for j in range(2, n):  # 第三个子数组的左端点\n",
    "            if 3*sum[j] > 2*sum[n]:\n",
    "                break\n",
    "            \n",
    "            # sum[il] >= 2*sum[j] - sum[n]\n",
    "            while sum[il] < 2*sum[j] - sum[n]:\n",
    "                il += 1\n",
    "            \n",
    "            # sum[ir] <= sum[j]//2\n",
    "            while ir < j and sum[ir] <= sum[j]//2:\n",
    "                ir += 1\n",
    "            \n",
    "            # [il, ir]\n",
    "            ans += ir - il\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, a: List[int]) -> int:\n",
    "      \n",
    "        n = len(a)\n",
    "        sum_a = [0] * (n + 1)\n",
    "        for i, v in enumerate(a):\n",
    "            sum_a[i + 1] = sum_a[i] + v\n",
    "\n",
    "        # ans = 0\n",
    "        # for r in range(2, n + 1):\n",
    "        #     if 3 * sum_a[r] <= 2 * sum_a[n]:\n",
    "        #         l1 = sorted(range(1, r), key=lambda x: 2 * sum_a[r] - sum_a[n] - sum_a[x])[-1] \n",
    "        #         ans += sorted(range(l1, r), key=lambda x: (sum_a[r] // 2 + 1))[-1]\n",
    "\n",
    "        # return ans % (10**9 + 7)\n",
    "\n",
    "\n",
    "        \n",
    "        ans = 0\n",
    "        il = 1  # 第二个子数组的左端点\n",
    "        ir = 1\n",
    "        for j in range(2, n):  # 第三个子数组的左端点\n",
    "            if 3*sum_a[j] > 2*sum_a[n]:\n",
    "                break\n",
    "            \n",
    "            # sum[il] >= 2*sum[j] - sum[n]\n",
    "            while sum_a[il] < 2*sum_a[j] - sum_a[n]:\n",
    "                il += 1\n",
    "            \n",
    "            # sum[ir] <= sum[j]//2\n",
    "            while ir < j and sum_a[ir] <= sum_a[j]//2:\n",
    "                ir += 1\n",
    "            \n",
    "            # [il, ir]\n",
    "            ans += ir - il\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        s = [nums[0]]*len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            s[i] = s[i-1] + nums[i]\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            left = s[i]\n",
    "            idx1 = max(i+1, bisect.bisect_left(s, 2*left))\n",
    "            idx2 = min(len(nums)-1, bisect.bisect_right(s, (s[-1]+left)/2))\n",
    "     \n",
    "            ans = (ans + max(0,idx2 - idx1)) % (10**9+7)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        pre=list(accumulate(nums))\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            l=max(i+1,bisect_left(pre,pre[i]+pre[i]))\n",
    "            r=min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))\n",
    "            res=(res+max(0,r-l))%(10**9+7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + x\n",
    "        total = prefix_sum[-1]\n",
    "        right1 = right2 = 0\n",
    "        ans = 0\n",
    "\n",
    "        for left in range(n - 1):\n",
    "            x = prefix_sum[left + 1]\n",
    "            if right1 <= left + 1:\n",
    "                right1 = left + 2\n",
    "            while right1 < n and prefix_sum[right1] < 2 * x:\n",
    "                right1 += 1\n",
    "            if right1 >= n and prefix_sum[right1] < 2 * x:\n",
    "                break\n",
    "            while right2 < n and prefix_sum[right2] <= (total + x) // 2:\n",
    "                right2 += 1\n",
    "            ans += max(right2 - right1, 0)\n",
    "            print(left, right1, right2)\n",
    "        \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = [0] * n\n",
    "        p[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            p[i] = p[i-1] + nums[i]\n",
    "        ans = 0\n",
    "        mod = int(1e9+7)\n",
    "        for i in range(n-2):\n",
    "            l, r = i + 1, n - 2\n",
    "            left, mid, right = p[i], nums[i+1], p[-1] - p[i+1]\n",
    "            if left > 2 * (p[-1] - p[i]):\n",
    "                break\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                mid = p[m] - left\n",
    "                right = p[-1] - p[m]\n",
    "                if left <= mid <= right or mid > right:\n",
    "                    r = m\n",
    "                else :\n",
    "                    l = m + 1\n",
    "            mid, right = p[l] - left, p[-1] - p[l]\n",
    "            a,b = 0,0\n",
    "            if left <= mid <= right:\n",
    "                a = l\n",
    "            l, r = i + 1, n - 2\n",
    "            left, mid, right = p[i], nums[i+1], p[-1] - p[i+1]\n",
    "            while l < r:\n",
    "                m = (l + r + 1) >> 1\n",
    "                mid = p[m] - left\n",
    "                right = p[-1] - p[m]\n",
    "                if left <= mid <= right or mid < left:\n",
    "                    l = m\n",
    "                else :\n",
    "                    r = m - 1\n",
    "            mid, right = p[l] - left, p[-1] - p[l]\n",
    "            if left <= mid <= right:\n",
    "                b = l\n",
    "            if a and b:\n",
    "                ans = (ans + b - a + 1) % mod\n",
    "        return ans\n",
    "\n",
    "s = Solution()\n",
    "s.waysToSplit([1,2,2,2,5,0])  \n",
    "\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ps = list(accumulate(nums))\n",
    "\n",
    "        def check(mid):\n",
    "            return ps[-1] - ps[mid] >= ps[mid] - ps[i]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n - 2):\n",
    "            l = max(i + 1, bisect_left(ps, ps[i] * 2))\n",
    "            r = bisect_left(range(n - 1), 1, l, key=lambda t: not check(t)) - 1\n",
    "\n",
    "            if r >= l:\n",
    "                ans += r - l + 1\n",
    "                ans %= kmod\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        length = len(nums)\n",
    "        left, right = 0, 0\n",
    "        preSum = [0] * length\n",
    "        preSum[0] = nums[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, length):\n",
    "            preSum[i] = preSum[i - 1] + nums[i]\n",
    "        #print(preSum)\n",
    "        for i in range(length):\n",
    "            left = max(i + 1, bisect.bisect_left(preSum, 2 * preSum[i]))\n",
    "            right = min(length -1, bisect.bisect_right(preSum, (preSum[-1] + preSum[i])//2))\n",
    "            #print(left, right)\n",
    "            if left < right:\n",
    "                ans = (ans + right - left) % mod\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    可以采用 双指针 + 累加 循环\n",
    "    \"\"\"\n",
    "\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        pre = list(accumulate(nums))\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # l确定mid数组的左边界 r确定mid数组右边界\n",
    "            l = max(i + 1, self.get_left(pre, pre[i] * 2))\n",
    "            r = min(n - 1, self.get_right(pre, (pre[i] + pre[-1]) // 2))\n",
    "            res = res + max(0, r - l) % mod\n",
    "        return res % mod\n",
    "\n",
    "    def get_left(self, pre, x):\n",
    "        l, r = 0, len(pre) - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if pre[mid] < x:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "\n",
    "    def get_right(self, pre, x):\n",
    "        l, r = 0, len(pre) - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if pre[mid] > x:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        # presum = [0] * (len(nums) + 1)\n",
    "\n",
    "        # for i in range(1, len(presum)):\n",
    "        #     presum[i] = presum[i - 1] + nums[i - 1]\n",
    "        presum = [0] * (len(nums))\n",
    "        presum[0] = nums[0]\n",
    "\n",
    "        for i in range(1, len(presum)):\n",
    "            presum[i] = presum[i - 1] + nums[i]\n",
    "\n",
    "        sum_ = sum(nums)\n",
    "\n",
    "        for i in range(len(nums) - 2):\n",
    "            # L = presum[i + 1]\n",
    "            L = presum[i]\n",
    "            if L > 1/3 * sum_:\n",
    "                break\n",
    "            \n",
    "            # M >= 2L\n",
    "            left = i + 1\n",
    "            right = len(presum)\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "\n",
    "                if presum[mid] < 2 * L:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            \n",
    "            # if left == len(presum):\n",
    "            #     continue\n",
    "            idx1 = left\n",
    "\n",
    "            # M <= (sum_ + L) / 2\n",
    "\n",
    "            left = i\n",
    "            right = len(presum) - 2\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if presum[mid] > (sum_ + L) / 2:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            # if left == i:\n",
    "            #     continue\n",
    "            idx2 = left\n",
    "\n",
    "\n",
    "            res += (idx2 - idx1 + 1) if idx2 - idx1 + 1 >= 0 else 0\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        presum = [0]\n",
    "        total = 0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "            presum.append(total)\n",
    "        # presum[i] <= presum[j] - presum[i] \n",
    "        # so presum[j] >= 2* presum[i]\n",
    "        # presum[j] - presum[i] <= presum[-1] - presum[j] \n",
    "        # so presum[j] <= (presum[-1] + presum[i])/2\n",
    "        res = 0\n",
    "        #     1. 2. 3\n",
    "        #.   [1, 1, 1]\n",
    "        # [0, 1, 2, 3]\n",
    "        for i in range(1, len(presum)-2):\n",
    "            left = bisect.bisect_left(presum, 2*presum[i])\n",
    "            right = bisect.bisect_right(presum, (presum[-1] + presum[i])/2) \n",
    "            left = max(left, i +1)\n",
    "            right = min(right, len(presum)-1)\n",
    "            res += max(0, right - left)\n",
    "        return res % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "1. 先思考一个简单的问题：分成两个子数组\n",
    "s1\n",
    "s2 = sum(nums) - s1\n",
    "s1 <= s2\n",
    "s1 <= sum(nums) - s1\n",
    "\n",
    "2*s1 <= sum(nums)\n",
    "s1 <= sum(nums)//2\n",
    "\n",
    "2. 分成三个子数组\n",
    "枚举第三个子数组\n",
    "s1 + s2 + s3 = sum(nums)\n",
    "\n",
    "s1 + s2 = sum(nums) - s3\n",
    "s1 <= s2 <= sum(nums) - s1 - s2\n",
    "\n",
    "s1 <= s2\n",
    "s1 <= sum(nums) - 2*s2\n",
    "\n",
    "s1 <= s2 <= (sum(nums) - s1)//2\n",
    "\n",
    "在固定 s3 的前提下（s2 的右端点是固定的）\n",
    "有多少个合法的 s2\n",
    "求出 s2 的最小值（s2 左端点的最大值）\n",
    "求出 s2 的最大值（s2 左端点的最小值） 最小是 1\n",
    "\n",
    "s1 + s2 = sum(nums) - s3\n",
    "s1 <= s2\n",
    "得到 s2 的最小值 = (sum(nums) - s3 + 1) // 2\n",
    "\n",
    "s2 的最大值 = s3\n",
    "\n",
    "3. 用下标分析\n",
    "s3 = sum[n] - sum[j]\n",
    "s2 = sum[j] - sum[il]\n",
    "s2 <= s3  => sum[il] >= 2*sum[j] - sum[n]\n",
    "j 越大，il 越大\n",
    "\n",
    "s2 = sum[j] - sum[ir]\n",
    "s1 = sum[ir]\n",
    "s1 <= s2  => sum[ir] <= sum[j]//2\n",
    "j 越大，ir 越大\n",
    "\n",
    "j 的下界：2\n",
    "\n",
    "j 的上界\n",
    "sum[il] >= 2*sum[j] - sum[n]\n",
    "sum[ir] <= sum[j]//2\n",
    "=> 3*sum[j] <= 2*sum[n]\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sum = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            sum[i+1] = sum[i] + x\n",
    "        #print(sum)\n",
    "        ans = 0\n",
    "        il = 1  # 第二个子数组的左端点\n",
    "        ir = 0\n",
    "        for j in range(2, n):  # 第三个子数组的左端点\n",
    "            if 3*sum[j] > 2*sum[n]:\n",
    "                break\n",
    "            \n",
    "            # sum[il] >= 2*sum[j] - sum[n]\n",
    "            while sum[il] < 2*sum[j] - sum[n]:\n",
    "                il += 1\n",
    "            \n",
    "            # sum[ir] <= sum[j]//2\n",
    "            while ir+1 < j and sum[ir+1] <= sum[j]//2:\n",
    "                ir += 1\n",
    "            \n",
    "            # [il, ir]\n",
    "            #print(il, ir)\n",
    "\n",
    "            ans += ir - il + 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l = max(i+1, bisect_left(pre, pre[i]+pre[i]))\n",
    "            r = min(n-1, bisect_right(pre, (pre[i]+pre[-1])//2))\n",
    "            ans = (ans + max(0, r-l)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        # presum = [0] * (len(nums) + 1)\n",
    "\n",
    "        # for i in range(1, len(presum)):\n",
    "        #     presum[i] = presum[i - 1] + nums[i - 1]\n",
    "        presum = [0] * (len(nums))\n",
    "        presum[0] = nums[0]\n",
    "\n",
    "        for i in range(1, len(presum)):\n",
    "            presum[i] = presum[i - 1] + nums[i]\n",
    "\n",
    "        sum_ = sum(nums)\n",
    "\n",
    "        for i in range(len(nums) - 2):\n",
    "            # L = presum[i + 1]\n",
    "            L = presum[i]\n",
    "            if L > 1/3 * sum_:\n",
    "                break\n",
    "            \n",
    "            # M >= 2L\n",
    "            left = i + 1\n",
    "            right = len(presum)\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "\n",
    "                if presum[mid] < 2 * L:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            \n",
    "            if left == len(presum):\n",
    "                continue\n",
    "            idx1 = left\n",
    "\n",
    "            # M <= (sum_ + L) / 2\n",
    "\n",
    "            left = i\n",
    "            right = len(presum) - 2\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if presum[mid] > (sum_ + L) / 2:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "            if left == i:\n",
    "                continue\n",
    "            idx2 = left\n",
    "\n",
    "\n",
    "            res += (idx2 - idx1 + 1) if idx2 - idx1 + 1 >= 0 else 0\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        prefix = [0]\n",
    "        for num in nums:\n",
    "            prefix.append(prefix[-1]+num)\n",
    "        # prefix[i] <= prefix[j]-prefix[i] <= prefix[-1]-prefix[j]\n",
    "        # => prefix[i]*2 <= prefix[j] <= (prefix[-1]+prefix[i])/2\n",
    "        # find the range of j: lower <= j < upper\n",
    "        ways = 0\n",
    "        for i in range(1, len(prefix)-2):\n",
    "            # lower = lower bound of j\n",
    "            lower = bisect_left(prefix, prefix[i]*2) # prefix[i]*2 <= prefix[j]\n",
    "            # upper = (upper bound of j) + 1\n",
    "            upper = bisect_right(prefix, (prefix[-1]+prefix[i])/2) # prefix[j] <= (prefix[-1]+prefix[i])/2\n",
    "            # i+1 <= lower < upper <= len(prefix)-1\n",
    "            ways += max(0, min(upper, len(prefix)-1) - max(lower, i+1))\n",
    "        return ways % (10**9+7)\n",
    "# https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/discuss/999157/Python3-binary-search-and-2-pointer  \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        presums = list(itertools.accumulate(nums))\n",
    "        lo = mid = 1\n",
    "        res = 0\n",
    "        M = 10**9+7\n",
    "        for i in range(N-2):\n",
    "            lo = max(lo, i+1)\n",
    "            while lo <= N-2 and presums[lo]-presums[i] < presums[i]:\n",
    "                lo += 1\n",
    "            while mid <= N-2 and presums[-1]-presums[mid]>=presums[mid]-presums[i]:\n",
    "                mid += 1\n",
    "            if mid > lo:\n",
    "                res = (res+mid-lo)%M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        acc_sum = list()\n",
    "        all_sum = 0\n",
    "        for num in nums:\n",
    "            all_sum += num\n",
    "            acc_sum.append(all_sum)\n",
    "\n",
    "        ret_ways = 0\n",
    "        one_third_sum  = all_sum / 3.\n",
    "        left_cursor = 0\n",
    "        mid_cursor, right_cursor = 1, 1\n",
    "        while left_cursor < n - 2 and acc_sum[left_cursor] <= one_third_sum:\n",
    "            mid_cursor = max(mid_cursor, left_cursor + 1)\n",
    "            left_sum = acc_sum[left_cursor]\n",
    "            while mid_cursor < n - 1 and acc_sum[mid_cursor] - left_sum < left_sum:\n",
    "                mid_cursor += 1\n",
    "            while right_cursor < n - 2 and acc_sum[right_cursor+1] - left_sum <= all_sum - acc_sum[right_cursor+1]:\n",
    "                right_cursor += 1\n",
    "            ret_ways += right_cursor - mid_cursor + 1\n",
    "            left_cursor += 1\n",
    "        return ret_ways % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        pre_sum = list(accumulate(nums, initial = 0))\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        def check2(mid):\n",
    "            if pre_sum[n] - pre_sum[mid] >= pre_sum[mid] - pre_sum[i]:\n",
    "                return True\n",
    "            return False \n",
    "\n",
    "        def check1(mid):\n",
    "            if pre_sum[mid] - pre_sum[i] >= pre_sum[i]:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            l, r = i + 1, n - 1\n",
    "            if pre_sum[i] * 3 > pre_sum[n]: break\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if check1(mid): r = mid\n",
    "                else: l = mid + 1\n",
    "            x = l\n",
    "            l, r = i + 1, n - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if check2(mid): l = mid\n",
    "                else: r = mid - 1\n",
    "            y = l\n",
    "            #print(i, x, y, n)\n",
    "            if pre_sum[n] - pre_sum[y] >= pre_sum[y] - pre_sum[i] and pre_sum[x] - pre_sum[i] >= pre_sum[i]: ans += y - x + 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#从BF出发优化\n",
    "# 在前缀和上枚举两个指针\n",
    "# 优化：第一个指针确定后，可以根据数学关系，列出不等式，从而是用二分确定第二个指针的范围\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums:List[int]) -> int:\n",
    "        #  查找nums中>=target的第一个位置\n",
    "        n=len(nums)\n",
    "        # 计算前缀和\n",
    "        summ=[0]*n\n",
    "        summ[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            summ[i]=summ[i-1]+nums[i]\n",
    "\n",
    "        def lower_bound(start,target):\n",
    "            l,r=start,n-1\n",
    "            if l>r:\n",
    "                return -1\n",
    "            while l<r:\n",
    "                # print(l,r)\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l\n",
    "\n",
    "        def upper_bound(start,target):\n",
    "            l,r=start,n-1\n",
    "            if l>r:\n",
    "                return -1\n",
    "            while l<r:\n",
    "                # print(l,r)\n",
    "                mid=((r-l)>>1)+l\n",
    "                if summ[mid]<=target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l-1\n",
    "        \n",
    "        \n",
    "        # 枚举第一个指针\n",
    "        ans=0\n",
    "        mod=int(1e9+7)\n",
    "        for i in range(n):\n",
    "            # lower_bound:sum[j]-sum[i]>=sum[i]=>\n",
    "            # 2*sum[i]<=sum[j]\n",
    "            if 3*summ[i]>summ[n-1]:\n",
    "                break\n",
    "            left=lower_bound(i+1,2*summ[i])\n",
    "            if left==-1:\n",
    "                continue\n",
    "            print(\"left:\",left,\"i:\",i)\n",
    "            # sum[n]-sum[j]>=sum[j]-sum[i]\n",
    "            # =>2*sum[j]<=sum[n]+sum[i]\n",
    "            right=upper_bound(i+1,(summ[n-1]+summ[i])*0.5)\n",
    "            if right==-1:\n",
    "                continue\n",
    "            print(\"right:\",right)\n",
    "            ans=(ans%mod+(right-left+1)%mod)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        presums = list(itertools.accumulate(nums))\n",
    "        lo = mid = 1\n",
    "        res = 0\n",
    "        M = 10**9+7\n",
    "        for i in range(N-2):\n",
    "            lo = max(lo, i+1)\n",
    "            while lo <= N-2 and presums[lo]-presums[i] < presums[i]:\n",
    "                lo += 1\n",
    "            mid = max(mid, lo)\n",
    "            while mid <= N-2 and presums[-1]-presums[mid]>=presums[mid]-presums[i]:\n",
    "                mid += 1\n",
    "            if mid > lo:\n",
    "                res = (res+mid-lo)%M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i3 in range(2, n):  # 遍历第3段的开头\n",
    "            s3 = s[n] - s[i3]\n",
    "            if s3 * 3 < s[-1]:\n",
    "                break\n",
    "            s12 = s[-1] - s3\n",
    "            # s1 的范围 [max(0, s12-s3), s12 // 2]\n",
    "            p1 = max(bisect_left(s, max(0, s12 - s3)), 1)  # p1不能取0，否则第一段的长度为0\n",
    "            p2 = bisect_right(s, s12 // 2)\n",
    "            p2 = min(p2, i3)\n",
    "            ans += (p2 - p1)\n",
    "            ans %= MOD\n",
    "            # print(i3, p1, p2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "      prefix = [0]\n",
    "      for num in nums:\n",
    "        prefix.append(prefix[-1]+num)\n",
    "      res = 0\n",
    "      n = len(nums)\n",
    "      for i in range(n-2):\n",
    "        left = bisect.bisect_left(prefix, 2*prefix[i+1])\n",
    "        left = max(left, i+2)\n",
    "        limit = min((prefix[i+1]+prefix[-1])//2, prefix[-1] - prefix[i+1])\n",
    "        right = bisect.bisect_right(prefix, limit)\n",
    "        right = min(right, n)\n",
    "        # print(i, left, right)\n",
    "        res += max(0, right - left)\n",
    "      return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToSplit(self, nums: List[int]) -> int:\n",
    "        def bi_small(nums,target,left=0,right=len(nums)-1):\n",
    "            # 在nums中寻找不超过target的最大索引\n",
    "            if nums==[] or nums[left]>target:\n",
    "                return -1\n",
    "            while left<right:\n",
    "                mid=left+(right-left+1)//2\n",
    "                if nums[mid]<=target:\n",
    "                    left=mid\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            return left\n",
    "        \n",
    "        def bi_large(nums,target,left=0,right=len(nums)-1):\n",
    "            # 在nums中寻找不小于target的最小索引\n",
    "            if nums==[] or nums[right]<target:\n",
    "                return -1\n",
    "            while left<right:\n",
    "                mid=left+(right-left)//2\n",
    "                if nums[mid]>=target:\n",
    "                    right=mid\n",
    "                else:\n",
    "                    left=mid+1\n",
    "            return left\n",
    "\n",
    "        # 首先计算前缀和\n",
    "        prefix=[]\n",
    "        n=len(nums)\n",
    "        summ=0\n",
    "        for num in nums:\n",
    "            summ+=num\n",
    "            prefix.append(summ)\n",
    "        # 然后从前缀和中确定分点\n",
    "        ans=0\n",
    "        for i in range(n-2):\n",
    "\n",
    "            left_idx=bi_large(prefix, target=2*prefix[i],left=i+1,right=n-2)\n",
    "            right_idx=bi_small(prefix, prefix[i]+(prefix[-1]-prefix[i])//2,left=i+1,right=n-2)\n",
    "            if left_idx!=-1 and right_idx!=-1 and right_idx>=left_idx:\n",
    "                ans=(ans+right_idx-left_idx+1)%(10**9+7)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
